package com.c2b.algorithm.leetcode.hot100;

/**
 * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/description/">合并 K 个升序链表</a>
 * <p>给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。</p>
 * <pre>
 * 示例 1：
 *      输入：lists = [[1,4,5],[1,3,4],[2,6]]
 *      输出：[1,1,2,3,4,4,5,6]
 *      解释：链表数组如下：
 *          [
 *              1->4->5,
 *              1->3->4,
 *              2->6
 *          ]
 *      将它们合并到一个有序链表中得到。
 *          1->1->2->3->4->4->5->6
 *
 * 示例 2：
 *      输入：lists = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：lists = [[]]
 *      输出：[]
 * </pre>
 * <b>提示：</b>
 * <li>k == lists.length</li>
 * <li>0 <= k <= 10^4</li>
 * <li>0 <= lists[i].length <= 500</li>
 * <li>-10^4 <= lists[i][j] <= 10^4</li>
 * <li>lists[i] 按 升序 排列</li>
 * <li>lists[i].length 的总和不超过 10^4</li>
 *
 * @author c2b
 * @since 2023/4/19 9:50
 */
public class Hot023MergeKLists_H {

    /**
     * 思路：合并两个链表
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (ListNode listNode : lists) {
            ans = mergeTwoLists(ans, listNode);
        }
        return ans;
    }

    /**
     * 合并两个有序链表
     *
     * @param listNode1 链表1
     * @param listNode2 链表2
     */
    private ListNode mergeTwoLists(ListNode listNode1, ListNode listNode2) {
        if (listNode1 == null || listNode2 == null) {
            return listNode1 != null ? listNode1 : listNode2;
        }
        ListNode dummy = new ListNode(0);
        ListNode currNode = dummy;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val <= listNode2.val) {
                currNode.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                currNode.next = listNode2;
                listNode2 = listNode2.next;
            }
            currNode = currNode.next;
        }
        currNode.next = listNode1 != null ? listNode1 : listNode2;
        return dummy.next;
    }
}
